package 弗洛伊德Floyd算法;

import java.util.Arrays;

public class 弗洛伊德Floyd算法 {
	public static void main(String[] args) {
		//顶点数组
		char[] vertex = {'A','B','C','D','E','F','G'};
		//邻接矩阵
		int[][] matrix = new int[7][7];
		int N = 65535;
		matrix[0]=new int[] {0,5,7,N,N,N,2};
		matrix[1]=new int[]{5,0,N,9,N,N,3};
		matrix[2]=new int[] {7,N,0,N,8,N,N}; 
		matrix[3]=new int[] {N,9,N,0,N,4,N}; 
		matrix[4]=new int[]{N,N,8,N,0,5,4};
		matrix[5]=new int[] {N,N,N,4,5,0,6};
		matrix[6]=new int[] {2,3,N,N,4,6,0};
		
		//创建图
		Graph graph = new Graph(vertex.length, matrix, vertex);
		graph.floyd();
		graph.show();
	}
}

//创建图
class Graph {
	
	//存放顶点数组
	char[] vertex;
	//保存距离的数组
	int[][] dis;
	//保存前驱的数组
	char[][] pre;
	
	/**
	 * 构造器
	 * @param length 长度
	 * @param matrix 邻接矩阵
	 * @param vertex 顶点数组
	 */
	public Graph(int length, int[][] matrix, char[] vertex) {
		//初始化
		this.vertex = vertex;
		this.dis = matrix;
		this.pre = new char[length][length];
		//pre初始化，初始为每行都是它自己
		for(int i = 0; i < length; i++) {
			Arrays.fill(pre[i], vertex[i]);
		}
	}
	
	/**
	 * 弗洛伊德算法
	 */
	public void floyd() {
		//保存距离
		int len = 0;
		
		//中间结点 k [A,B,C,D,E,F,G]
		for(int k = 0; k < dis.length; k++) {
			//起始结点 i [A,B,C,D,E,F,G]
			for (int i = 0; i < dis.length; i++) {
				//目标结点 j [A,B,C,D,E,F,G]
				for (int j = 0; j < dis.length; j++) {
					//从顶点出发，经过中间顶点，到达目标顶点（i - k - j）
					len = dis[i][k] + dis[k][j];
					//判断len是否小于直接到达的路径（i - j）
					if(len < dis[i][j]) {
						//小于则更新距离和前驱
						dis[i][j] = len;
						pre[i][j] = pre[k][j];
					}
				}
			}	
		}
	}
	
	/**
	 * 输出
	 */
	public void show() {
		//输出距离和前驱
		for(int i = 0; i < dis.length; i++) {
			for(int j = 0; j < dis[0].length; j++) {
				System.out.print(pre[i][j] + "\t");
			}
			System.out.println();
			for(int j = 0; j < dis[0].length; j++) {
				System.out.print(dis[i][j] + "\t");
			}
			System.out.println();
			System.out.println();
		}
	}
}